package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GrayCode {

	public static void main(String[] args) {
		GrayCode code = new GrayCode();
		System.out.println(code.grayCode(4));
	}
	public List<Integer> grayCodeBad(int n) {
		List<Integer > list = new ArrayList<Integer>();
		char[] nums = new char[n];
		Arrays.fill(nums, '0');
		backTrack(list, n, nums);
		return list;
	}
	//bad idea, can't solve the problem
	public void backTrack(List<Integer> list, int n, char[] nums){
		if(n == 0){
			list.add(getValueFromBinary(nums));
			return;
		}
		for(int i = 0; i <= 1; i++){
		}
	}
	public int getValueFromBinary(char[] nums){
		int num = 0;
		for(int i = 0; i < nums.length; i++){
			num += (nums[i] - '0') * (1 << (nums.length - 1 - i));
		}
		return num;
	}

	
//	n = 0: 0
//	n = 1: 0, 1
//	n = 2: 00, 01, 11, 10  (0, 1, 3, 2)
//	n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)
//	发现规律没有，前面的都是一样的，后面是 2的n - 1 次方倒序加上前面的
//	以n = 3为例： 4 + 2 = 6, 4 + 3 = 7, 4 + 1 = 5, 4 + 0 = 4 
//	we can easy get the n = 4
//	0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8
	public  List<Integer> grayCode(int n) {
		List<Integer > list = new ArrayList<Integer>();
		if(n < 0){
			return list;
		}
		if(n == 0){
			list.add(0);
			return list;
		}
		List<Integer> last = grayCode(n - 1);
		int number = 1 << (n - 1);
		list.addAll(last);
		for(int i = 0; i < number; i++){
			list.add(last.get(number - 1 - i) + number);
		}
		return list;
	}
	
	//上面的都不算啥，接下来的这个才是王者，so brilliant
	public List<Integer> grayCode2(int n){
		List<Integer > list = new ArrayList<Integer>();
		int size = 1 << n;  // 1的0次方为1
		for(int i = 0; i < size; i++){
//			list.add((i / 2 )^ i);  //除二就是右移一位，此时再亦或只会在前一个的基础上改变一位
			list.add((i >> 1) ^ i);
		}
		return list;
	}
}
